OSPF (Open Shortest Path First) routing protocol is the predominant intra-domain routing protocol in the Internet. OSPF is a link-state routing protocol. In operation all routers running OSPF in a single area advertise the status of each of their links in a link-status message in a Link-State Advertisement (LSA) with a sequence number to indicate the time progression of multiple such messages from the same node. This message is sent on a hop-by-hop basis to all routers running OSPF within the area. For each link that fails, both end-points of the link (if they are still up) will generate a LSA message to be sent all over the network. Therefore, for each link failure, a node will get at most two unique LSAs per failure (not counting duplicate LSAs).
Since OSPF runs over the IP protocol, each node has information on all the IP-level links in the network area. This information includes the end-points of the link, the status of the link, the type of the link (e.g., point-to-point, broadcast), as well as the cost metric of the link. Using this information and the well-known Djikstra's Shortest Path Tree algorithm, a node will compute the best possible (least-cost) routes to every other node in the area. There can be multiple such areas within a single network domain. Routers advertise route summary LSAs between areas via so-called border routers that straddle multiple areas.
Message Overhead
OSPF standards dictate that all routers in an area running OSPF must receive a link status change notification from any OSPF router in the same area.
In the following disclosure for exemplary purposes the use of the term router assumes a network packet switching node assumed to be running OSPF and that all routers are in a single routing area.
Each LSA, when received by a router, is checked for duplicates. If it is not a duplicate, the LSA is flooded by the router on all its interfaces, other than the one on which the LSA was received. When all routers have a plurality of links (in a well-connected topology), many of these LSAs will be duplicate LSAs. Parsing these multiple duplicates takes significant time and delays the transmission of original/unique LSAs across the network. This delays network convergence to the order of several minutes in the worst case in rich network topologies seen in provider networks.
Therefore, it would be desirable to have a method and/or system capable of reducing the number of duplicate LSAs such that network convergence times are improved.